package top.fengleifeng.question;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.question
 * @Description:
 * @date Date : 2021年01月04日 5:56 下午
 */
public class Num509斐波那契数 {

    class Solution {

        public int fib(int n) {
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, 0);
            map.put(1, 1);
            return get(n, map);
        }

        private int get(int n, Map<Integer, Integer> map) {

            if (map.containsKey(n)) {
                return map.get(n);
            }
            int num = get(n - 1, map) + get(n - 2, map);
            map.put(n, num);
            return num;
        }

    }

    public static void main(String[] args) {
        int fib = new Num509斐波那契数().new Solution().fib(3);
        System.out.println(fib);
    }
}
